import re
import copy
import operator

class LexerToken:
  def __init__( self, type, value ):
    self.type = type
    self.value = value
    
  def __eq__( self, token ):
    return self.type == token.type and self.value == token.value
    
  def __repr__( self ):
    return 'LexerToken( %s, \'%s\' )' % ( self.type, self.value )

class LexerRule:
  def __init__( self, name, pattern, ignore = False ):
    self.name = name
    self.pattern = pattern
    self.ignore = ignore
    self.rule = re.compile( self.pattern )
    
  def __repr__( self ):
    return 'LexerRule( %s, \'%s\' )' % ( self.name, self.pattern )
    
  def __eq__( self, rule ):
    return self.name == rule.name and self.pattern == rule.pattern and self.ignore == rule.ignore
    
  def apply( self, s ):
    m = self.rule.match( s )
    if m and m.start() == 0:
      return LexerToken( self.name, s[:m.end()] )

class Lexer:
  def __init__( self, rules ):
    self.rules = rules
    self.ruleMap = dict( [ ( rule.name, rule ) for rule in self.rules ] )
    
  def __repr__( self ):
    return 'Lexer( %s )' % self.rules
    
  def lex( self, s ):
    tokens = []
    pos = 0
    while pos < len( s ):
      results = filter( lambda result: result[1], [ ( rule, rule.apply( s[pos:] ) ) for rule in self.rules ] )
      assert len( results ) == 1, 'parse error: %s, %s' % ( tokens, s[pos:] )
      if not results[0][0].ignore:
        tokens.append( results[0][1] )
      pos += len( results[0][1].value )
    return tokens
    
  @staticmethod
  def test():
    lexer = Lexer( [ LexerRule( 'ws', '\s+' ), 
                     LexerRule( 'num', '\d+\.?\d*' ),
                     LexerRule( 'id', '[a-zA-Z][\w_-]*' ),
                     LexerRule( 'str', '\".*\"' ),
                   ] )
    assert lexer.lex( '12 \n3.14 foo21_-bar "hello world"' ) == [
             LexerToken( 'num', '12' ), 
             LexerToken( 'ws', ' \n' ), 
             LexerToken( 'num', '3.14' ),
             LexerToken( 'ws', ' ' ), 
             LexerToken( 'id', 'foo21_-bar' ),
             LexerToken( 'ws', ' ' ), 
             LexerToken( 'str', '"hello world"' ), 
           ]
           
class ParserResult:
  def __init__( self, type, value, children ):
    self.type = type
    self.value = value
    self.children = children
    
  def __repr__( self, tabs = '' ):
    return '%s%s %s\n%s' % ( tabs, self.type, self.value, ''.join( [ child.__repr__( tabs + '  ' ) for child in self.children ] ) )
    
  def __eq__( self, result ):
    return self.type == result.type and self.value == result.value and self.children == result.children
    
class ParserRule:
  AND = 'AND'
  OR = 'OR'
  LITERAL = 'LITERAL'
  ONEORMORE = 'ONEORMORE'
  ZEROORMORE = 'ZEROORMORE'
  
  def __init__( self, type, name, children ):
    self.type = type
    self.name = name
    self.children = children
    
  def __repr__( self, tabs = '' ):
    return '%s%s %s\n%s' % ( tabs, self.type, self.name, ''.join( [ child.__repr__( tabs + '  ' ) for child in self.children ] ) )
    
  def apply( self, tokens ):
    if self.type == ParserRule.LITERAL:
      if tokens and tokens[0].type == self.name:
        return ParserResult( self.name, tokens[0].value, [] ), tokens[1:]
        
    elif self.type == ParserRule.AND:
      if len( tokens ) >= len( self.children ):
        childTokens = copy.copy( tokens )
        childResults = []
        for child in self.children:
          childResult = child.apply( childTokens )
          if not childResult:
            return
          childResults.append( childResult[0] )
          childTokens = childResult[1]
        return ParserResult( self.name, None, childResults ), childTokens
        
    elif self.type == ParserRule.OR:
      for child in self.children:
        childResult = child.apply( copy.copy( tokens ) )
        if childResult:
          return ParserResult( self.name, None, [ childResult[0] ] ), childResult[1]
          
    elif self.type == ParserRule.ONEORMORE:
      assert len( self.children ) == 1
      childResult = self.children[0].apply( tokens )
      if childResult:
        childResults = [ childResult[0] ]
        childTokens = childResult[1]
        while True:
          childResult = self.children[0].apply( copy.copy( childTokens ) )
          if childResult:
            childResults.append( childResult[0] )
            childTokens = childResult[1]
          else:
            return ParserResult( self.name, None, childResults ), childTokens
            
    elif self.type == ParserRule.ZEROORMORE:
      assert len( self.children ) == 1
      childResults = []
      childTokens = tokens
      while True:
        childResult = self.children[0].apply( copy.copy( childTokens ) )
        if childResult:
          childResults.append( childResult[0] )
          childTokens = childResult[1]
        else:
          return ParserResult( self.name, None, childResults ), childTokens
          
    else:
      raise RuntimeError( 'invalid parser rule type %s' % self.type )
      
class Parser:
  def __init__( self, lexer, rules ):
    self.lexer = lexer
    self.root = rules[0]
    
    rules += [ ParserRule( ParserRule.LITERAL, rule.name, [] ) for rule in self.lexer.rules ]
    ruleMap = dict( [ ( rule.name, rule ) for rule in rules ] )
    for rule in ruleMap.values():
      for i in range( len( rule.children ) ):
        child = rule.children[i]
        if isinstance( child, str ):
          if child in ruleMap:
            child = rule.children[i] = ruleMap[ child ]
          else:
            raise RuntimeError( 'unknown rule %s' % rule.children[i] )
        child.parent = rule
    
  def __repr__( self ):
    return 'Parser( %s, %s )' % ( self.lexer, self.root )
    
  def parse( self, s ):
    result = self.root.apply( self.lexer.lex( s ) )
    if not result:
      raise RuntimeError( 'failed to parse' )
    elif result[1]:
      raise RuntimeError( 'leftover tokens: result = %s, tokens = %s' % result )
    else:
      return result[0]
      
  @staticmethod
  def load( s ):
    parser = Parser( 
      Lexer( [ 
        LexerRule( 'ws', '\s+', True ),
        LexerRule( 'id', '[a-zA-Z][\w_-]*' ),
        LexerRule( 'str', '\'.*\'' ),
        LexerRule( 'semicolon', ';' ),
        LexerRule( 'equals', '=' ),
        LexerRule( 'star', '\*' ),
        LexerRule( 'plus', '\+' ),
        LexerRule( 'bar', '\|' ),
        LexerRule( 'tilde', '\~' ),
      ] ),
      [
        ParserRule( ParserRule.ONEORMORE, 'grammar', [ 'line' ] ),
        ParserRule( ParserRule.AND, 'line', [ 'id', 'equals', 'rule', 'semicolon' ] ),
        ParserRule( ParserRule.OR, 'rule', [ 'orRule', 'oneOrMoreRule', 'zeroOrMoreRule', 'lexerRule', 'negativeLexerRule', 'andRule' ] ),
        ParserRule( ParserRule.AND, 'orRule', [ 'id', 'orRuleContent' ] ),
        ParserRule( ParserRule.ONEORMORE, 'orRuleContent', [ 'orRuleContentIter' ] ),
        ParserRule( ParserRule.AND, 'orRuleContentIter', [ 'bar', 'id' ] ),
        ParserRule( ParserRule.AND, 'oneOrMoreRule', [ 'id', 'plus' ] ),
        ParserRule( ParserRule.AND, 'zeroOrMoreRule', [ 'id', 'star' ] ),
        ParserRule( ParserRule.AND, 'lexerRule', [ 'str' ] ),
        ParserRule( ParserRule.AND, 'negativeLexerRule', [ 'tilde', 'str' ] ),
        ParserRule( ParserRule.ONEORMORE, 'andRule', [ 'id' ] ),
      ] )

    grammar = parser.parse( s )
    
    lexerRules = []
    rules = []
    for line in grammar.children:
      id = line.children[0].value
      rule = line.children[2].children[0]
      if rule.type == 'lexerRule':
        lexerRules.append( LexerRule( id, rule.children[0].value[1:-1] ) )
      elif rule.type == 'negativeLexerRule':
        lexerRules.append( LexerRule( id, rule.children[1].value[1:-1], True ) )
      elif rule.type == 'orRule':
        ids = [ rule.children[0].value ] + [ iter.children[1].value for iter in rule.children[1].children ]
        rules.append( ParserRule( ParserRule.OR, id, ids ) )
      elif rule.type == 'andRule':
        ids = [ child.value for child in rule.children ]
        rules.append( ParserRule( ParserRule.AND, id, ids ) )
      elif rule.type == 'oneOrMoreRule':
        rules.append( ParserRule( ParserRule.ONEORMORE, id, [ rule.children[0].value ] ) )
      elif rule.type == 'zeroOrMoreRule':
        rules.append( ParserRule( ParserRule.ZEROORMORE, id, [ rule.children[0].value ] ) )
      else:
        raise RuntimeError( 'unknown rule type %s' % rule.type )
        
    return Parser( Lexer( lexerRules ), rules )
    
  @staticmethod
  def test():
    parser = Parser.load( '''
      ws = ~'\s+';
      num = '\d+\.?\d*';
      id = '[a-zA-Z][\w_-]*';
      str = '\".*\"';
      lparen = '\(';
      rparen = '\)';
      expr = parenExpr | id | num | str;
      parenExpr = lparen exprContent rparen;
      exprContent = expr+;
    ''' )
    
    assert ParserResult( 'expr', None, [
      ParserResult( 'parenExpr', None, [
        ParserResult( 'lparen', '(', [] ),
        ParserResult( 'exprContent', None, [
          ParserResult( 'expr', None, [
            ParserResult( 'id', 'foo', [] ),
          ] ),
          ParserResult( 'expr', None, [
            ParserResult( 'num', '3.14', [] ),
          ] ),
          ParserResult( 'expr', None, [
            ParserResult( 'str', '"hello"', [] ),
          ] ),
        ] ),
        ParserResult( 'rparen', ')', [] ),
      ] ),
    ] ) == parser.parse( '( foo 3.14 "hello" )' )
    
class LispExpr:
  VAR = 'VAR'
  NUM = 'NUM'
  STR = 'STR'
  LIST = 'LIST'

  def __init__( self, type, value ):
    self.type = type
    self.value = value
    
  def __repr__( self ):
    return 'LispExpr( %s, %s)' % ( self.type, self.value )
    
class LispValue:
  NUM = 'NUM'
  STR = 'STR'
  FUNC = 'FUNC'
  
  def __init__( self, type, value ):
    self.type = type
    self.value = value
    
  def __repr__( self ):
    return 'LispValue( %s, %s )' % ( self.type, self.value )
    
  def __eq__( self, value ):
    return self.type == value.type and self.value == value.value
    
class LispInterpreter:
  def __init__( self ):
    self.parser = Parser.load( '''
      ws = ~'\s+';
      num = '\d+\.?\d*';
      id = '[a-zA-Z][\w_-]*';
      str = '\".*\"';
      lparen = '\(';
      rparen = '\)';
      program = expr*;
      expr = parenExpr | id | num | str;
      parenExpr = lparen exprContent rparen;
      exprContent = expr+;
    ''' )
    
  def run( self, s ):
    program = self.parser.parse( s )
    env = {}
    vals = [ self.eval( self.convertExpr( expr ), env ) for expr in program.children ]
    return vals[-1]
    
  def convertExpr( self, expr ):
    value = expr.children[0]
    if value.type == 'id':
      return LispExpr( LispExpr.VAR, value.value )
    elif value.type == 'num':
      if '.' in value.value:
        return LispExpr( LispExpr.NUM, LispValue( LispValue.NUM, float( value.value ) ) )
      else:
        return LispExpr( LispExpr.NUM, LispValue( LispValue.NUM, int( value.value ) ) )
    elif value.type == 'str':
      return LispExpr( LispExpr.STR, LispValue( LispValue.STR, value.value[1:-1] ) )
    elif value.type == 'parenExpr':
      return LispExpr( LispExpr.LIST, [ self.convertExpr( child ) for child in value.children[1].children ] )
    else:
      raise RuntimeError
    
  def eval( self, expr, env ):
    if expr.type == LispExpr.VAR:
      assert expr.value in env, 'unknown var %s' % expr.value
      return env[expr.value]
    elif expr.type in ( LispExpr.NUM, LispExpr.STR ):
      return expr.value
    elif expr.type == LispExpr.LIST:
      return self.apply( expr.value[0], expr.value[1:], env )
    else:
      raise RuntimeError
      
  def apply( self, functorExpr, argExprs, env ):
    if functorExpr.type == LispExpr.VAR:
      builtinName = 'builtin_%s' % functorExpr.value
      if hasattr( self, builtinName ):
        return getattr( self, builtinName )( argExprs, env )
    functor = self.eval( functorExpr, env )
    assert functor.type == LispValue.FUNC
    argNames, body = functor.value
    argValues = [ self.eval( argExpr, env ) for argExpr in argExprs ]
    assert len( argNames ) == len( argValues )
    funcEnv = copy.copy( env )
    for argName, argValue in zip( argNames, argValues ):
      funcEnv[ argName ] = argValue
    return self.eval( body, funcEnv )

  def builtin_def( self, args, env ):
    assert len( args ) == 2
    header = args[0]
    assert header.type == LispExpr.LIST
    nameExpr = header.value[0]
    assert nameExpr.type == LispExpr.VAR
    name = nameExpr.value
    argExprs = header.value[1:]
    assert all( [ argExpr.type == LispExpr.VAR for argExpr in argExprs ] )
    argNames = [ argExpr.value for argExpr in argExprs ]
    body = args[1]
    env[name] = LispValue( LispValue.FUNC, ( argNames, body ) )
    
  def builtin_add( self, args, env ):
    vals = [ self.eval( arg, env ) for arg in args ]
    assert all( [ val.type == vals[0].type for val in vals ] )
    result = vals[0].value
    for val in vals[1:]:
      result += val.value
    return LispValue( vals[0].type, result )
    
  def builtin_sub( self, args, env ):
    vals = [ self.eval( arg, env ) for arg in args ]
    assert all( [ val.type == vals[0].type for val in vals ] )
    result = vals[0].value
    for val in vals[1:]:
      result -= val.value
    return LispValue( vals[0].type, result )
    
  def builtin_mul( self, args, env ):
    vals = [ self.eval( arg, env ) for arg in args ]
    assert all( [ val.type == vals[0].type for val in vals ] )
    result = vals[0].value
    for val in vals[1:]:
      result *= val.value
    return LispValue( vals[0].type, result )
    
  def builtin_div( self, args, env ):
    vals = [ self.eval( arg, env ) for arg in args ]
    assert all( [ val.type == vals[0].type for val in vals ] )
    result = vals[0].value
    for val in vals[1:]:
      result /= val.value
    return LispValue( vals[0].type, result )
    
  @staticmethod
  def test():
    assert LispValue( LispValue.NUM, 4 ) == LispInterpreter().run( '( def ( sqrt x ) ( mul x x ) ) ( sqrt 2 )' )
    
if __name__ == '__main__':
  Lexer.test()
  Parser.test()
  LispInterpreter.test()
